package org.codetranslators.compiler.liveness;

import java.util.Vector;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import org.codetranslators.common.Temp;

public class InterferenceGraph extends Graph
{
	private ControlFlowGraph cfg;
	private BitSet liveIn[];
	private BitSet liveOut[];
	
	private int numNodes;
	private int numTemps;
	
	private HashMap keyVsNodes;
	private HashMap nodeVsTemps;
	private Vector igTemps;
	private HashMap adjacencyMatrix;    // Needed by the register allocator
	private HashMap moveRelatedNodes;   // Needed by the register allocator
	
	private HashMap tempVsLiveRanges;   // Needed by the register allocator;
										// will hold a map of each temporary against
										// a list of it's live ranges
	
	private HashMap tempVsPrevDefUsePair; // A map of each temporary vs. an two-element
										  // array of Integers; the first elements holds the line number
										  // the temp has been defined and the second holds the current use.
	
	private HashMap nodesVsSpillCosts;
	private int maxSpillCostForAnyTemp;
	
	public InterferenceGraph(ControlFlowGraph cfg)
	{
		super(cfg.getNumTemps());
		this.cfg = cfg;
		
		numNodes = cfg.getNodeCount();
		numTemps = cfg.getNumTemps();
		igTemps = cfg.getTempsSet();
		liveIn = new BitSet[numNodes];
		liveOut = new BitSet[numNodes];
		for(int i = 0; i < numNodes; i++)
		{
			liveIn[i] = new BitSet(numTemps);
			liveIn[i].clear();
			liveOut[i] = new BitSet(numTemps);
			liveOut[i].clear();
		}
		
		keyVsNodes = new HashMap();
		nodeVsTemps = new HashMap();
		adjacencyMatrix = new HashMap();
		moveRelatedNodes = new HashMap();
		tempVsLiveRanges = new HashMap();
		tempVsPrevDefUsePair = new HashMap();
		nodesVsSpillCosts = new HashMap();
		
		createInterferenceGraph();
	}
	
	/*
	 * This method will reset all the attributes of the interference graph, so the register
	 * allocator can start all over again. Does not reset live-in and live-out information since this
	 * is not required
	 * 
	 */
	
	public void reset()
	{
		numNodes = 0;
		numTemps = 0;
		igTemps = new Vector();
		
		keyVsNodes = new HashMap();
		nodeVsTemps = new HashMap();
		adjacencyMatrix = new HashMap();
		moveRelatedNodes = new HashMap();
		tempVsLiveRanges = new HashMap();
		tempVsPrevDefUsePair = new HashMap();
		nodesVsSpillCosts = new HashMap();
	}
	
	private void createInterferenceGraph()
	{
		Vector cfgNodes = cfg.nodes();
	
		int count = 0;
		
		BitSet liveInTemp[] = new BitSet[numNodes];
		BitSet liveOutTemp[] = new BitSet[numNodes];
		
		do
		{
			// Start by iterating backwards
			for(int i = numNodes -1; i >= 0; i--)
			{
				liveInTemp[i] = (BitSet) liveIn[i].clone();
				liveOutTemp[i] = (BitSet) liveOut[i].clone();
				
				Node node = (Node) cfgNodes.elementAt(i);
				liveOut[i] = getLiveOutForNode(node);
				liveIn[i] = getLiveInForNode(node, i);
			}
			
			count++;
		}while(!isEndOfIterations(liveInTemp, liveOutTemp));
		
		// Now that live in and live out are calculated for each node, create the
		// interference graph. This is done by adding edges from the def temporaries to 
		// the live-out temporaries for each node
		for(int i = 0; i < numNodes; i++)
		{
			Node cfgNode = (Node) cfgNodes.elementAt(i);
			CfgProperties cfgProps = cfg.getCfgProperties(cfgNode);
			
			Vector defList = cfgProps.getDefList();
			Vector useList = cfgProps.getUseList();
			populateLiveRangeInfo(i, defList, useList);
			boolean isMove = cfgProps.isMove();
			
			Vector liveOutTemps = getLiveOutTemps(i);
			
			if(defList == null)  continue;
			int numDefs = defList.size();
			for(int j = 0; j < numDefs; j++)
			{
				Temp from = (Temp) defList.elementAt(j);
				Node fromNode = newInterferenceGraphNode(from);
				
				// If it is a move, add to move-related nodes
				if(isMove)
				{
					for(int a = 0; a < useList.size(); a++)
					{
						Node toNode = newInterferenceGraphNode((Temp) useList.elementAt(a));
						addToMoveRelatedNodes(fromNode, toNode); 
					}
				}
				
				// Add interference edges for this dest. node to each of the live-outs
				int numLiveOuts = liveOutTemps.size();
				for(int k = 0; k < numLiveOuts; k++)
				{
					Temp to = (Temp) liveOutTemps.elementAt(k);
					if(from == to) continue; 
					
					Node toNode = newInterferenceGraphNode(to);
					
					// Add an interference edge if it is not a move
					if(!isMove)
					{
						updateAdjacencyMatrix(fromNode, toNode);
					}
					else
					{
						if(!useList.contains(to)) updateAdjacencyMatrix(fromNode, toNode);
					}
				}	
				// TODO - Cleaner way to do this? If there are no interferences for a symbolic temporary, how 
				// should we make it part of the interference graph?
				if(fromNode.getSuccessors() == null || fromNode.getSuccessors().size() == 0)
				{
					// This node does not have any interference; make it interfere at least with FP
					Temp to = Temp.getTemp("FP");
					Node toNode = newInterferenceGraphNode(to);
					//addEdge(fromNode, toNode);
					updateAdjacencyMatrix(fromNode, toNode);
				}
			}
		}
		// Now that the interference graph has been created, populate the spill costs
		populateSpillCosts();
	}
	
	private BitSet getLiveInForNode(Node node, int index)
	{
		BitSet liveInForNode = new BitSet(numTemps);
		liveInForNode.clear();
		
		BitSet uses = cfg.getUsesBitVector(node);
		BitSet defs = cfg.getDefsBitVector(node);
		
		BitSet liveOutForNode = liveOut[index];
		BitSet usesClone = (BitSet) uses.clone();
		BitSet liveOutForNodeClone = (BitSet) liveOutForNode.clone();

		liveOutForNodeClone.andNot(defs);
		usesClone.or(liveOutForNodeClone);
		liveInForNode = usesClone;
		
		return liveInForNode;
	}
	
	private BitSet getLiveOutForNode(Node node)
	{	
		BitSet liveOutForNode = new BitSet(numTemps);
		liveOutForNode.clear();	
		
		Vector succs = node.getSuccessors();
		if(succs != null && succs.size() > 0)
		{
			for(int j = 0; j < succs.size(); j++)
			{
				Node succ = (Node) succs.elementAt(j);
				int index = getNodeIndexFromNode(succ);
				BitSet succLiveIn = liveIn[index];
				liveOutForNode.or(succLiveIn);
			}
		}
		return liveOutForNode;
	}
	
	private boolean isEndOfIterations(BitSet liveInTemp[], BitSet liveOutTemp[])
	{
		for(int i = 0; i < numNodes; i++)
		{
			BitSet tempIn = liveInTemp[i];
			BitSet tempOut = liveOutTemp[i];
			
			for(int j = 0; j < numTemps; j++)
			{
				if(tempIn.get(j) != liveIn[i].get(j)) return false;
				if(tempOut.get(j) != liveOut[i].get(j)) return false;
			}		
		}
		return true;
	}
	
	private int getNodeIndexFromNode(Node node)
	{
		Vector cfgNodes = cfg.nodes();
		for(int i = 0; i < numNodes; i++)
		{
			Node nd = (Node) cfgNodes.elementAt(i);
			if(nd == node) return i;
		}
		return -1;
	}
	
	private int getTempIndexFromTemp(Temp temp)
	{
		int i;
		for(i = 0; i < numTemps; i++)
		{
			Temp t = (Temp) igTemps.elementAt(i);
			if(t == temp) return i;
		}
		igTemps.addElement(temp);
		
		numTemps = igTemps.size();
		
		return i;
	}
	
	public void addToMoveRelatedNodes(Node from, Node to)
	{
		HashSet destNodesForFrom = (HashSet) moveRelatedNodes.get(from);
		if(destNodesForFrom == null)  destNodesForFrom = new HashSet();
		destNodesForFrom.add(to);
		moveRelatedNodes.put(from, destNodesForFrom);
		
		HashSet destNodesForTo = (HashSet) moveRelatedNodes.get(to);
		if(destNodesForTo == null)  destNodesForTo = new HashSet();
		destNodesForTo.add(from);
		moveRelatedNodes.put(to, destNodesForTo);
	}
	
	public void showLiveInAndLiveOut()
	{
		for(int i = 0; i < numNodes; i++)
		{
			String displayForNode = i + ": ";
			
			BitSet li = liveIn[i];
			BitSet lo = liveOut[i];
			
			String liveInStr = "Live In -> ";
			String liveOutStr = "  Live Out -> ";
			for(int j = 0; j < numTemps; j++)
			{
				if(li.get(j))
				{
					liveInStr += cfg.getTemp(j).toString() + " ";
				}
				if(lo.get(j))
				{
					liveOutStr += cfg.getTemp(j).toString() + " ";
				}
			}

			displayForNode += liveInStr + liveOutStr;
			
			System.out.println(displayForNode);
		}
	}
	
	private Vector getLiveOutTemps(int index)
	{
		Vector liveOutTemps = new Vector();
		BitSet liveOutBitSet = liveOut[index];
		for(int i = 0; i < numTemps; i++)
		{
			if(liveOutBitSet.get(i)) liveOutTemps.addElement(cfg.getTemp(i));
		}
		return liveOutTemps;
	}
	
	public Node newInterferenceGraphNode(Temp temp)
	{
		int tempIndex = getTempIndexFromTemp(temp);
		String id = "" + tempIndex;
		
		Node node = (Node) keyVsNodes.get(id);
		
		if(node != null) return node;
		
		//	This node does not exist already; create a new one
		return createNewNode(temp, id);
	}
	
	public Node createNewNode(Temp temp, String id)
	{
		Node node = super.newNode(id);
		keyVsNodes.put(id, node);
		nodeVsTemps.put(node, temp);
		return node;
	}
	
	public Temp getTemp(Node node)
	{
		return (Temp) nodeVsTemps.get(node);
	}
	
	public void updateAdjacencyMatrix(Node fromNode, Node toNode)
	{
		// Add "toNode" to the adjacent list of "fromNode"
		HashSet adjListForFromNode = (HashSet )adjacencyMatrix.get(fromNode);
		if(adjListForFromNode == null) adjListForFromNode = new HashSet();
		adjListForFromNode.add(toNode);
		adjacencyMatrix.put(fromNode, adjListForFromNode);
		
		// Add "fromNode" to the adjacent list of "toNode"
		HashSet adjListForToNode = (HashSet )adjacencyMatrix.get(toNode);
		if(adjListForToNode == null) adjListForToNode = new HashSet();
		adjListForToNode.add(fromNode);
		adjacencyMatrix.put(toNode, adjListForToNode);
	}
	
	public Vector getIgTemps()
	{
		return igTemps;
	}
	
	public HashSet getAdjacentNodeList(Node node)
	{
		return (HashSet) adjacencyMatrix.get(node);
	}
	
	public void removeNode(Node node)
	{
		// Removes the edges, from the adjacency matrix but not from the node list
		HashSet adjacentList = (HashSet)adjacencyMatrix.get(node);  // Get the adjacent nodes
		if(adjacentList != null)
		{
			// (It could be null if two nodes that coalesce to create this input node do 
			// not have any neighbors)
			Iterator iter = adjacentList.iterator();
			while(iter.hasNext())
			{
				Node toNode = (Node) iter.next();
				HashSet adjacentListForTo = (HashSet)adjacencyMatrix.get(toNode);
				adjacentListForTo.remove(node);
			}
		}
		
		// Remove from the adjacency matrix also
		adjacencyMatrix.remove(node);
		
		// Remove from the node Vs. Temps map too
		nodeVsTemps.remove(node);
		
	}
	
	public void showInterferenceGraph()
	{
		String str = "";
		for(int i = 0; i < nodes().size(); i++)
		{
			Node node = (Node) nodes().elementAt(i);
			if(node == null) continue;
			Temp temp = (Temp) nodeVsTemps.get(node);
			if(temp == null) continue;
			str += temp.toString() + " has edges to: ";
			
			HashSet nbrs = (HashSet) adjacencyMatrix.get(node);
			if(nbrs == null)
			{
				str += "\n";
				continue;
			}
			Iterator iter = nbrs.iterator();
			while(iter.hasNext())
			{
				Node nxt = (Node) iter.next();
				Temp tp = (Temp) nodeVsTemps.get(nxt);
				str += tp.toString() + " ";
			}
			
			 str += "\n";
		}
		
		System.out.println(str);
	}
	
	public HashSet getMoveRelatedNodes(Node nd)
	{
		return (HashSet) moveRelatedNodes.get(nd);
	}
	
	private void populateLiveRangeInfo(int line, Vector defList, Vector useList)
	{
		// Inspect the defintions
		if(defList != null)
		{
			int numDefs = defList.size();

			for(int i = 0; i < numDefs; i++)
			{
				Temp tempDef = (Temp) defList.elementAt(i);
				Integer[] prevDefUsePair = (Integer[]) tempVsPrevDefUsePair.get(tempDef);
				if(prevDefUsePair == null)
				{
					// This is the first time the temp is being defined; create the def-use pair
					Integer [] defUsePair = new Integer[2];
					defUsePair[0] = new Integer(line);
					defUsePair[1] = null;
					tempVsPrevDefUsePair.put(tempDef, defUsePair);
				}
				else
				{
					// This temp. has been defined (and probably used earlier). Check if its been used earlier
					if(prevDefUsePair[1] == null)
					{
						// This temp is being redefined before getting used; update the def index
						prevDefUsePair[0] = new Integer(line);
					}
					else
					{
						// This temp is being redefined after it has been defined and used; create the new live range
						// and update the new def-use pair
						addToLiveRanges(tempDef, prevDefUsePair);
						
						Integer [] defUsePair = new Integer[2];
						defUsePair[0] = new Integer(line);
						defUsePair[1] = null;
						tempVsPrevDefUsePair.put(tempDef, defUsePair);
					}
				}
			}
		}
		
		if(useList != null)
		{
			// Inspect the usages
			int numUses = useList.size();
			for(int i = 0; i < numUses; i++)
			{
				Temp tempUse = (Temp) useList.elementAt(i);
				Integer[] prevDefUsePair = (Integer[]) tempVsPrevDefUsePair.get(tempUse);
				if(prevDefUsePair == null)
				{
					// Temp is being used without being defined; ignore the def, could be a physical register
					Integer [] defUsePair = new Integer[2];
					defUsePair[0] = null;
					defUsePair[1] = new Integer(line);
					tempVsPrevDefUsePair.put(tempUse, defUsePair);
				}
				else
				{
					// Update the latest usage linenum
					prevDefUsePair[1] = new Integer(line);
				}
				// Update the live ranges map for the temp
				addToLiveRanges(tempUse, prevDefUsePair);
			}
		}
	}
	
	public void addToLiveRanges(Temp temp, Integer[] defUsePair)
	{
		Vector liveRanges = (Vector) tempVsLiveRanges.get(temp);
		if(liveRanges == null) liveRanges = new Vector();
		liveRanges.addElement(defUsePair);
		tempVsLiveRanges.put(temp, liveRanges);
	}
	
	public void populateSpillCosts()
	{
		Vector igNodes = nodes();
		int numIgNodes = igNodes.size();
		for(int n = 0; n < numIgNodes; n++)
		{
			Node igNode = (Node) igNodes.elementAt(n);
			Temp temp = (Temp) nodeVsTemps.get(igNode);
			
			// Get the maximum live range for this node
			int maxLiveRange = 0;
			Vector liveRanges = (Vector) tempVsLiveRanges.get(temp);
			if(liveRanges != null) // Could be null for reserved registers like $FP, $SP
			{
				int numLiveRanges = liveRanges.size();
				for(int i = 0; i < numLiveRanges; i++)
				{
					Integer[] defUse = (Integer[])liveRanges.elementAt(i);
					if(defUse != null)
					{
						int defLine = 0, useLine = 0;
						if(defUse[0] != null) defLine = defUse[0].intValue();
						if(defUse[1] != null) useLine = defUse[1].intValue();
						
						int diff = Math.abs(useLine - defLine);
						if(diff > maxLiveRange) maxLiveRange = diff;
					}
				}
				
				// Get the degree of this temp node
				int degree = getDegree(igNode);
				int spillCost = degree * maxLiveRange;
				
				// Populate the node vs. spill cost and the max spill cost for any temp node
				nodesVsSpillCosts.put(igNode, "" + spillCost);
				if(spillCost >= maxSpillCostForAnyTemp) maxSpillCostForAnyTemp = spillCost;
			}
		}
	}
	
	public String getSpillCost(Node node)
	{
		String spillCost = (String) nodesVsSpillCosts.get(node);
		if(spillCost == null) return "-1";
		return spillCost;
	}
	
	public void setSpillCost(Node node, String cost)
	{
		nodesVsSpillCosts.put(node, cost);
	}
	
	public int getMaxSpillCost()
	{
		return maxSpillCostForAnyTemp;
	}
	
	public int getDegree(Node node)
	{
		HashSet neighbors = (HashSet)adjacencyMatrix.get(node);
		if(neighbors != null) return neighbors.size();
		return 0;
	}
	
	public void showMoveRelatedNodes()
	{
		System.out.println("MOVE RELATED NODES: ");
		String str = "";
		for(int i = 0; i < numTemps; i++)
		{
			Node node = (Node) keyVsNodes.get("" + i);
			if(node == null) continue;
			Temp temp = (Temp) nodeVsTemps.get(node);
			if(temp == null) continue;
			
			HashSet mvNodes = (HashSet) moveRelatedNodes.get(node);
			str += temp.toString() + " is move-related to: ";
			if(mvNodes != null)
			{
				Iterator iter = mvNodes.iterator();
				while(iter.hasNext())
				{
					Node nxt = (Node) iter.next();
					Temp tp = (Temp) nodeVsTemps.get(nxt);
					str += tp.toString() + " ";
				}
			}
			 str += "\n";
		}
		
		System.out.println(str);
	}

	public void showLiveRangeInfo()
	{
		System.out.println("LIVE RANGE INFO: ");
		
		for(int i = 0; i < nodes().size(); i++)
		{
			Node nd = (Node)nodes().elementAt(i);
			Temp tmp = (Temp)nodeVsTemps.get(nd);
			System.out.print(tmp.toString() + ": " );
			
			Vector liveRanges = (Vector) tempVsLiveRanges.get(tmp);
			String rangeStr = "";
			if(liveRanges != null)
			{
				for(int a = 0; a < liveRanges.size();a++)
				{
					Integer[] range = (Integer[]) liveRanges.elementAt(a);
					if(range != null)
					{
						String from = "?";
						String to = "?";
						if(range[0] != null) from = "" + range[0].intValue();
						if(range[1] != null) to = "" + range[1].intValue();
						rangeStr += "[" + from + " - " + to + "] ";
					}
				}
			}
			rangeStr += " Spill priority = " + nodesVsSpillCosts.get(nd);
			System.out.println(rangeStr);
		}
	}
	
}
